#include<iostream>
#include<assert.h>
using namespace std;

int Fibonaci(int n)
{
	if (n == 0)
		return 0;
	if (n == 1 || n == 2)
		return 1;
	return Fibonaci(n - 1) + Fibonaci(n - 1);
}
int Fibonaci_1(int n)
{
	int* F = new int[n + 1];
	F[0] = 1;
	F[0] = 1;
	for (int i = 2; i <= n; ++i)
	{
		F[i] = F[i - 1] + F[i - 2];
	}
	return F[n];
}
int main()
{
	Fibonaci_1(3);
	return 0;
};